package com.hfb.mashibing.alip8.diamondsquarealgorithm;

import java.util.Arrays;

/**
 * 荷兰国旗问题：
 * 给定一个整数数组，给定一个值K，这个值在原数组中一定存在，
 * 要求把数组中小于K的元素放到数组的左边，大于K的元素放到数组的右边，
 * 等于K的元素放到数组的中间，
 * 最终返回一个整数数组，其中只有两个值，分别是等于K的数组部分的左右两个下标值。
 *
 * 处理过程：
 * less 用于记录小于 4 的区域的右下标，初始为-1，代表不存在
 * more 用于记录大于 4 区域的左下标，初始为9，代表不存在
 * L 用于正在遍历的元素的下标，初始值为0
 * 从 arr[L] 即 arr[0] 开始遍历数组
 * 如果 arr[L] > 4, 交换 arr[++ less] 和 arr[L++] 的值
 * 如果 arr[L] < 4, 交换 arr[--more] 和 arr[L] 的值
 * 如果 arr[L] = 4, 不交换，L++，直接遍历下一个值
 * 当 L >= more，退出循环。
 *
 */
public class test01_DutchFlag {
    public static int[] partition(int[] arr, int L, int R, int p) {
        int less = L - 1;
        int more = R + 1;
        while(L < more) {
            if(arr[L] < p) {
                swap(arr, ++less, L++);
            } else if (arr[L] > p) {
                swap(arr, --more, L);
            } else {
                L++;
            }
        }
        return new int[] { less + 1, more - 1 };
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 1, 9, 7, 6, 1, 4, 5};
        int k = 4;
        System.err.println(Arrays.toString(
            partition(arr, 0, arr.length-1, k)));
    }

}
